package com.axzh.interview.algorithm;

public class RodCut {

	public static void main(String[] args) {
		int[] p = {1,5,8,9,10,17,17,20,24,30};
		RodCut.cutRod(p, 7);
	}
	
	public static void cutRod(int[] p, int n) {
		int[] result = new int[n+1];
		result[0]=0;
		for(int i=1;i<n+1;i++) {
			//int q=Integer.MIN_VALUE;
			for(int j=1;j<=i;j++) {
				result[i] =Math.max(result[i], result[i-j]+p[j-1]);
			}
			//result[i]=q;
		}
		for(int i:result) {
			System.out.print(i+" ");
		}
	}

}
